package 算法.搜索算法;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-09
 */
public class JZ44数字序列中某一位的数字 {
    //位数减法
    public int findNthDigit (int n) {
        // write code here
        //记录n是几位数
        int digit = 1;
        //记录当前位数区间的起始数字：1,10,100...
        long start = 1;
        //记录当前区间之前总共有多少位数字
        long sum = 9;
        //将n定位在某个位数的区间中
        while(n > sum){
            n -= sum;
            start *= 10;
            digit++;
            //该区间的总共位数
            sum = 9 * start * digit;
        }
        //定位n在哪个数字上
        String num = "" + (start + (n - 1) / digit);
        //定位n在数字的哪一位上
        int index = (n - 1) % digit;
        return (int)(num.charAt(index)) - (int)('0');
    }

    //添0补齐法
    public int findNthDigit2 (int n) {
        //记录n是几位数
        int i = 1;
        while(i * Math.pow(10, i) < n){
            //前面添0增加的位
            n += Math.pow(10, i);
            i++;
        }
        String num = "" + (n / i);
        //根据除法锁定目标数字，根据取模锁定位置
        return (int)(num.charAt(n % i)) - (int)('0');
    }

    public int findNthDigit3 (int n) {
        int digit= 1;
        long start = 1;
        long count = 9;
        while (n > count) {
            n -= count;
            digit += 1;
            start *= 10;
            count = 9*digit*start;
        }
        long num = start + (n-1)/digit;
        // 第三步
        return Long.toString(num).charAt((n-1)%digit) - '0';
    }
}
